package org.example.leetcode;

/**
 * @version 1.0.0
 * @author: lynn
 * @description: 最长公共序列
 * @date: 2021/7/26 10:38
 */
public class LC1143 {
    public static void main(String[] args) {

    }

    /**
     * 理论：
     * https://www.bilibili.com/video/BV14A411v7mP?from=search&seid=17697542267558938433
     * https://www.bilibili.com/video/BV1tB4y1M7zP?from=search&seid=17697542267558938433
     * 动态规划的方法讲解视频，主要考虑到状态转移方程
     *
     * 实践： https://www.bilibili.com/video/BV19U4y1p7Ew?from=search&seid=17697542267558938433
     * @return
     */
    public int longestCommonSubsequence(String text1, String text2) {
        int row=text1.length();
        int col=text2.length();
        int[][] dp=new int[row+1][col+1];
        //fixme 对着实践视频中的卡表就知道为什么要 i<=row,i<=col 还有就是 dp[row+1][col+1]，i,j要从1开始
        for (int i = 1; i <=row ; i++) {
            for (int j = 1; j <=col ; j++) {
                char c1=text1.charAt(i);
                char c2=text2.charAt(j);
                if (c1==c2){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else {
                    dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j]);
                }
            }
        }
        return dp[row][col];
    }
}
